DAY 1

1)

Starting array:
      {5, 2, 8, 1, 4}


   PASS 1
   -------

   Compare 5 and 2:
      5 > 2, so swap.
      {2, 5, 8, 1, 4}

   Compare 5 and 8:
      5 < 8, so no swap.
      {2, 5, 8, 1, 4}

   Compare 8 and 1:
      8 > 1, so swap.
      {2, 5, 1, 8, 4}

   Compare 8 and 4:
      8 > 4, so swap.
      {2, 5, 1, 4, 8}


   PASS 2
   -------

   Compare 2 and 5:
      2 < 5, so no swap.
      {2, 5, 1, 4, 8}

   Compare 5 and 1:
      5 > 1, so swap.
      {2, 1, 5, 4, 8}

   Compare 5 and 4:
      5 > 4, so swap.
      {2, 1, 4, 5, 8}


   PASS 3
   -------

   Compare 2 and 1:
      2 > 1, so swap.
      {1, 2, 4, 5, 8}

   Compare 2 and 4:
      2 < 4, so no swap.
      {1, 2, 4, 5, 8}

   Compare 4 and 5:
      4 < 5, so no swap.
      {1, 2, 4, 5, 8}


   PASS 4
   -------

   Compare 1 and 2:
      1 < 2, so no swap.

   Compare 2 and 4:
      2 < 4, so no swap.

   Compare 4 and 5:
      4 < 5, so no swap.

   Final array:
      {1, 2, 4, 5, 8}


   Total comparisons: 10
   Total swaps: 5

2) 

     public static void sortArr(int[] arr, int n) {
              for (int i = 0; i < n - 1; i++) {
                  for (int j = 0; j < n - 1 - i; j++) {
    
                      if (arr[j] > arr[j + 1]) {
                          int temp = arr[j];
                          arr[j] = arr[j + 1];
                          arr[j + 1] = temp;
                      }
                  }
              }
          }
    
    
       Complete program:
    
          public class BubbleSort {
    
              public static void sortArr(int[] arr, int n) {
                  for (int i = 0; i < n - 1; i++) {
                      for (int j = 0; j < n - 1 - i; j++) {
    
                          if (arr[j] > arr[j + 1]) {
                              int temp = arr[j];
                              arr[j] = arr[j + 1];
                              arr[j + 1] = temp;
                          }
                      }
                  }
              }
    
              public static void printArray(int[] arr) {
                  for (int i = 0; i < arr.length; i++) {
                      System.out.print(arr[i] + " ");
                  }
                  System.out.println();
              }
    
              public static void main(String[] args) {
                  int[] arr = {1, 5, 3, 2};
    
                  System.out.println("Before sorting:");
                  printArray(arr);
    
                  sortArr(arr, arr.length);
    
                  System.out.println("After sorting:");
                  printArray(arr);
              }
          }
    
       Output:
    
          Before sorting:
          1 5 3 2
    
          After sorting:
          1 2 3 5
    
    
       CHALLENGE:
    
       Modify the method so that it stops early when an entire pass makes no
       swaps.
    
          public static void sortArr(int[] arr, int n) {
              for (int i = 0; i < n - 1; i++) {
    
                  boolean swapped = false;
    
                  for (int j = 0; j < n - 1 - i; j++) {
    
                      if (arr[j] > arr[j + 1]) {
                          int temp = arr[j];
                          arr[j] = arr[j + 1];
                          arr[j + 1] = temp;
    
                          swapped = true;
                      }
                  }
    
                  if (!swapped) {
                      break;
                  }
              }
          }

----------------------------------------------------------------------------------------

DAY 2

1) 

    public static void selectionSort(int[] numbers) {

          for (int i = 0; i < numbers.length - 1; i++) {

              int minIndex = i;

              for (int j = i + 1; j < numbers.length; j++) {

                  if (numbers[j] < numbers[minIndex]) {
                      minIndex = j;
                  }
              }

              int temp = numbers[i];
              numbers[i] = numbers[minIndex];
              numbers[minIndex] = temp;
          }
      }

       Complete program:

      public class SelectionSort {

          public static void selectionSort(int[] numbers) {

              for (int i = 0; i < numbers.length - 1; i++) {

                  int minIndex = i;

                  for (int j = i + 1; j < numbers.length; j++) {

                      if (numbers[j] < numbers[minIndex]) {
                          minIndex = j;
                      }
                  }

                  int temp = numbers[i];
                  numbers[i] = numbers[minIndex];
                  numbers[minIndex] = temp;
              }
          }

          public static void printArray(int[] numbers) {
              for (int i = 0; i < numbers.length; i++) {
                  System.out.print(numbers[i] + " ");
              }
              System.out.println();
          }

          public static void main(String[] args) {
              int[] numbers = {64, 25, 12, 22, 11};

              System.out.println("Before sorting:");
              printArray(numbers);

              selectionSort(numbers);

              System.out.println("After sorting:");
              printArray(numbers);
          }
      }

   Output:

      Before sorting:
      64 25 12 22 11

      After sorting:
      11 12 22 25 64

2) 

int[] numbers = {29, 10, 14, 37, 13};


   1. Bubble Sort

      Starting array:
      {29, 10, 14, 37, 13}

      PASS 1:

      29 > 10, swap:
      {10, 29, 14, 37, 13}

      29 > 14, swap:
      {10, 14, 29, 37, 13}

      29 < 37, no swap:
      {10, 14, 29, 37, 13}

      37 > 13, swap:
      {10, 14, 29, 13, 37}


      PASS 2:

      10 < 14, no swap:
      {10, 14, 29, 13, 37}

      14 < 29, no swap:
      {10, 14, 29, 13, 37}

      29 > 13, swap:
      {10, 14, 13, 29, 37}


      PASS 3:

      10 < 14, no swap:
      {10, 14, 13, 29, 37}

      14 > 13, swap:
      {10, 13, 14, 29, 37}


      PASS 4:

      10 < 13, no swap:
      {10, 13, 14, 29, 37}

      Final array:

      {10, 13, 14, 29, 37}

      Total swaps: 4


   2. Selection Sort

      Starting array:
      {29, 10, 14, 37, 13}


      PASS 1:
      Find the smallest value in the entire array: 10

      Swap 10 with 29:

      {10, 29, 14, 37, 13}


      PASS 2:
      Find the smallest value in the remaining portion:
      {29, 14, 37, 13}

      Smallest value: 13

      Swap 13 with 29:

      {10, 13, 14, 37, 29}


      PASS 3:
      Find the smallest value in:
      {14, 37, 29}

      Smallest value: 14

      No swap is necessary.

      {10, 13, 14, 37, 29}


      PASS 4:
      Find the smallest value in:
      {37, 29}

      Smallest value: 29

      Swap 29 with 37:

      {10, 13, 14, 29, 37}


      Final array:

      {10, 13, 14, 29, 37}


      Number of actual swaps: 3

      Note: If the program always performs the swap, including when the
      minimum is already in the correct position, there would be 4 swap
      operations. A well-designed Selection Sort can avoid the unnecessary
      swap when minIndex == i.


   3. How many swaps does each algorithm make?

      Bubble Sort:     4 swaps
      Selection Sort:  3 actual swaps


   4. Which algorithm made fewer swaps?

      Selection Sort made fewer swaps for this particular array.

3)

    public class StudentSort {

          public static void printStudents(String[] names, int[] scores) {
              for (int i = 0; i < names.length; i++) {
                  System.out.println(names[i] + ": " + scores[i]);
              }
          }


          // Bubble Sort by name
          public static void bubbleSortByName(String[] names, int[] scores) {

              for (int i = 0; i < names.length - 1; i++) {

                  for (int j = 0; j < names.length - 1 - i; j++) {

                      if (names[j].compareTo(names[j + 1]) > 0) {

                          // Swap names
                          String tempName = names[j];
                          names[j] = names[j + 1];
                          names[j + 1] = tempName;

                          // Swap corresponding scores
                          int tempScore = scores[j];
                          scores[j] = scores[j + 1];
                          scores[j + 1] = tempScore;
                      }
                  }
              }
          }


          // Selection Sort by score, highest to lowest
          public static void selectionSortByScore(String[] names, int[] scores) {

              for (int i = 0; i < scores.length - 1; i++) {

                  int maxIndex = i;

                  for (int j = i + 1; j < scores.length; j++) {

                      if (scores[j] > scores[maxIndex]) {
                          maxIndex = j;
                      }
                  }

                  // Swap scores
                  int tempScore = scores[i];
                  scores[i] = scores[maxIndex];
                  scores[maxIndex] = tempScore;

                  // Swap corresponding names
                  String tempName = names[i];
                  names[i] = names[maxIndex];
                  names[maxIndex] = tempName;
              }
          }


          public static void main(String[] args) {

              String[] names = {
                "Grace", "Carlos", "Alice", "Henry", "Diana",
                "Jack", "Elena", "Brian", "Iris", "Frank"
              };

              int[] scores = {
                  94, 85, 92, 82, 96,
                  75, 71, 78, 89, 88
              };


              System.out.println("Original Student Data");
              System.out.println("---------------------");
              printStudents(names, scores);


              System.out.println("\nSorted Alphabetically");
              System.out.println("---------------------");

              bubbleSortByName(names, scores);
              printStudents(names, scores);


              // Reset arrays to their original order
              names = new String[] {
                  "Alice", "Brian", "Carlos", "Diana", "Elena",
                  "Frank", "Grace", "Henry", "Iris", "Jack"
              };

              scores = new int[] {
                  92, 78, 85, 96, 71,
                  88, 94, 82, 89, 75
              };


              System.out.println("\nSorted by Score (Highest to Lowest)");
              System.out.println("----------------------------------");

              selectionSortByScore(names, scores);
              printStudents(names, scores);
          }
      }


   Expected alphabetical order:

      Alice: 92
      Brian: 78
      Carlos: 85
      Diana: 96
      Elena: 71
      Frank: 88
      Grace: 94
      Henry: 82
      Iris: 89
      Jack: 75


   Expected score order:

      Diana: 96
      Grace: 94
      Alice: 92
      Iris: 89
      Frank: 88
      Carlos: 85
      Henry: 82
      Brian: 78
      Jack: 75
      Elena: 71


   CHALLENGE:

   Add a method to calculate the average score:

      public static double getAverage(int[] scores) {
          int sum = 0;

          for (int i = 0; i < scores.length; i++) {
              sum += scores[i];
          }

          return ((double) sum) / scores.length;
      }


   To find the highest-scoring student:

      System.out.println(
          names[0] + " has the highest score: " + scores[0]
      );


   To find the lowest-scoring student after sorting highest-to-lowest:

      int last = scores.length - 1;

      System.out.println(
          names[last] + " has the lowest score: " + scores[last]
      );


   The average score for the sample data is:

      85.0